/*
 * Main.java
 *
 * This file is part of FUJIWARA.
 * Copyright (C) 2010 Loris Fichera    (loris.fichera@gmail.com)
 *                    Daniele Marletta (danielemar86@gmail.com)
 *
 * FUJIWARA is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * FUJIWARA is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with FUJIWARA.  If not, see <http://www.gnu.org/licenses/>.
 */

package graphclient;

import java.util.ArrayList;
import java.util.Random;

/**
 *
 * @author Loris Fichera
 * @author Daniele Marletta
 *
 */
public class Main {

    private static void printHelp() {
        System.out.println ("usage: java -jar GraphClient.jar [Options]");
                System.out.println ("Options:");
                System.out.println ("  --help, -h                 print this message");
                System.out.println ("  --debug                    enable debug prints");
                System.out.println ("  --node_number <number>     set number of nodes");
                System.out.println ("  --graph_model <type>       set the graph model");
                System.out.println ("  --output, -o  <path>       set output path");
                System.out.println ();
                System.out.println ("<type> may be one of the following:");
                System.out.println ("  r                          a random graph");
                System.out.println ("  ws                         a barabasi-albert graph");
                System.out.println ("  ba                         a barabasi-albert graph");
    }

    public static void main (String[] args) {

        int       SIZE       = 100;
        GraphType GRAPH_TYPE = GraphType.RANDOM;
        boolean   DEBUG_BG   = false;
        boolean   DEBUG_FG   = true;
        String    path       = null;
        

        try {
        for (int i = 0; i < args.length; i ++) {
            
            if (args[i].equals("--help") || args[i].equals("-h")) {
                printHelp();
                return;
            
            } else if (args[i].equals("--node_number")) {

                SIZE = Integer.parseInt(args[i+1].toString());

            } else if (args[i].equals("--graph_model")) {

                if (args[i + 1].equals("r")) {
                    
                    GRAPH_TYPE = GraphType.RANDOM;
                    
                } else if(args[i + 1].equals("ws")) {

                    GRAPH_TYPE = GraphType.WATTS_STROGATZ;

                } else if (args[i + 1].equals("ba")) {

                    GRAPH_TYPE = GraphType.BARABASI_ALBERT;

                }

            } else if (args[i].equals("--debug")) {

                DEBUG_BG = true;
            }  else if (args[i].equals("--output") || args[i].equals("-o")) {

                path = args[i + 1];

            }
        }
        } catch (Exception e) {
            printHelp();
            return;
        }

        if (DEBUG_FG)  System.out.println ("Application Starting.");
        if (DEBUG_FG)
            if (args.length == 0)
                System.out.println ("Using default values...");
        if (DEBUG_FG)  System.out.println ("Nodes      : " + SIZE + ".");
        if (DEBUG_FG)  System.out.println ("Graph model: " + GRAPH_TYPE + ".");

        int [][] adjMatrix = GraphUtils.GenerateAdjMatrix (SIZE, GRAPH_TYPE);

        if (DEBUG_BG) {
            System.out.println ("Adjacency Matrix:");
            for ( int i = 0; i < adjMatrix.length; i ++ ) {
                for ( int j = 0; j < adjMatrix[i].length; j++ ) {
                    System.out.print (adjMatrix[i][j] + " ");
                }
                System.out.print ("\n");
            }
        }

        if (DEBUG_BG)  System.out.println("Invoking countNeighbours()");

        /** Step 1: count neighbours. */
        GraphPartitioningStrategy strategy = new DistributedGraphPartitioning ();
        int [] neighboursCount = strategy.countNeighbours (adjMatrix);

        if (DEBUG_BG) {
            System.out.println("countNeighbours() result:");
            for ( int i = 0; i < neighboursCount.length; i ++ ) {
                System.out.println (neighboursCount[i]);
            }
         }

        if (DEBUG_BG)  System.out.println("Invoking processConnections()");


        /** Step 2:  classify by connections number. */
        String [] connectionVector = strategy.processConnections(neighboursCount);

        /** Identify hypernodes. */
        ArrayList<Integer> hyperNodeIndexes = new ArrayList<Integer>();
        for ( int i = 0; i < connectionVector.length; i++ ) {
            if (connectionVector[i].equals("IC")) {
                hyperNodeIndexes.add(i);
            }
        }

        if (DEBUG_FG) {
            System.out.print("There are  "+ hyperNodeIndexes.size() + "  IC: ");
            for (int i=0; i<hyperNodeIndexes.size();i++) {
                System.out.print(hyperNodeIndexes.get(i) +" ");
            }
            System.out.println();
        }

        /** Step 3: compute hops count. */
        int [] adjVector = GraphUtils.squareMatrixToVector (adjMatrix);
        GraphThread [] threads = new GraphThread[hyperNodeIndexes.size()];
        for (int i = 0; i < threads.length; i ++) {
            threads[i] = new GraphThread (adjVector,
                                          neighboursCount,
                                          hyperNodeIndexes.get(i),
                                          new DistributedGraphPartitioning());
            threads[i].start();
        }

        // wait for threads to terminate
        try { 

            for (GraphThread t : threads) {
                t.join();
            }

        } catch (Exception e) {
            System.out.println("Error in joining thread.");
        }

        /** Retrieve the propagation array for each hypernode. */
        int [][] propagationArrays = new int[threads.length][];
        
        for ( int i = 0; i < threads.length; i ++) {
            propagationArrays[i] = threads[i].getHops();
        }

        /** Print propagation arrays. */
        if (DEBUG_BG) {
            for (int i = 0; i < propagationArrays.length; i ++) {
                for (int j = 0; j < propagationArrays[i].length; j ++ ) {
                    System.out.print(propagationArrays[i][j] + " ");
                }
                System.out.println();
            }
        }

        /** Step 4: classify nodes. */
        String [] partitionVector = classifyNodes(propagationArrays);

        /*
        for ( String i : partitionVector) {
            System.out.print(i + " ");
        }*/

        if (DEBUG_FG) System.out.println ("\nGenerating output...");
        //GraphUtils.GenerateDotSource("./../Graphviz/outputGraph.dot",adjMatrix,connectionVector,partitionVector);
        GraphUtils.GenerateNetworkXSource (path, null, adjMatrix,
                                           connectionVector,
                                           partitionVector);

        if (DEBUG_FG) System.out.println ("Done.");
    }



    public static String [] classifyNodes(int [][] propagationArrays) {

        int numClasses = propagationArrays.length;
        int numNodes = propagationArrays[0].length;

        if (numClasses == 0) {
            System.out.println("Warning: There are no IC nodes" );
        } else if (numClasses == numNodes) {
            System.out.println("Warning: All nodes are IC nodes" );
        }

        /** Return value of this method. */
        String [] partitionVector = new String[numNodes];

        /** Transpose the propagationArrays matrix, to simplify following
         * computation.
         */
        int [][] propagationT = new int [numNodes][numClasses];
        for (int row=0; row<numClasses; row++) {
            for (int column=0; column<numNodes; column++) {
                propagationT[column][row] = propagationArrays[row][column];
            }
        }

        int [] hopValues = new int[numClasses];
        int [] clusterSize = new int[numClasses];

        for (int i=0;i<clusterSize.length;i++) {
            clusterSize[i] = 0;
        }

        for (int row=0; row<numNodes; row++) {
            Integer min = Integer.MAX_VALUE;
            ArrayList<Integer> bestClusters = new ArrayList<Integer>();
            ArrayList<Integer> bestClustersSize = new ArrayList<Integer>();

            hopValues = propagationT[row];

            for (Integer hop : hopValues) {
                /** The current node is not reachable from the hypernode. */
                if ( hop < 0 ) hop = Integer.MAX_VALUE;
                /** Select min value of hops. */
                if ( hop < min ) {
                    min = hop;
                }
            }

            /** The current node in not reachable from no one of the hypernode. */
           /* if (min == Integer.MAX_VALUE) {
                System.out.print("  Min hop: " + "U" + " ");
            } else {
                System.out.print("  Min hop: " + min + " ");
            }*/

            /** Select the class with the min hop value or resolve conflicts. */
            for (int j = 0; j<hopValues.length;j++) {
                Integer currentHop = hopValues[j];
                /** The current hop is the minimum hop or the node is always unreachable. */
                if ( (currentHop==min) || (min== Integer.MAX_VALUE) ) {

                    if (bestClusters.isEmpty()) {
                        bestClusters.add(j);
                        bestClustersSize.add(clusterSize[j]);
                    } else {
                        /** Insert the cluster in the list following the increasing order of current class memebers. */
                        int index = 0;
                        while ( (index < bestClustersSize.size()) &&
                                (clusterSize[j] > bestClustersSize.get(index))
                                 )
                        {
                            index++;
                        }
                        bestClusters.add(index,j);
                        bestClustersSize.add(index,clusterSize[j]);
                    }
                }
            }

            Integer winnerClassID;
            /** There is a unique class with the minimum number of hop. */
            if ( bestClusters.size() == 1) {
                winnerClassID = bestClusters.get(0);
                clusterSize[winnerClassID.intValue()] += 1;
                partitionVector[row] = winnerClassID.toString();
            } else {
            /** There are multiple classes with the same number of minimum hops. */
                winnerClassID = resolveClash(bestClusters,bestClustersSize);
                clusterSize[winnerClassID.intValue()] += 1;
                partitionVector[row] = winnerClassID.toString();
            }

            //System.out.println("   Winner Class is: " + winnerClassID);

        } // End of loop: proceed with the next node.

        //System.out.println("Total class members: " +);
        for (int i=0; i< clusterSize.length; i++) {
             System.out.println("Class " + i + " has " + clusterSize[i] + " members");
        }
        //System.out.println();

        return partitionVector;
    }


    private static int resolveClash(ArrayList<Integer> rivalClusters, ArrayList<Integer> clusterSizes) {

        int numRivals = rivalClusters.size();
        int winner = -2;
        Random r = new Random();
        
        int totalMembers = 0;
        ArrayList<Integer> emptyClusters = new ArrayList<Integer>();
        
        for(int i=0; i<clusterSizes.size();i++) {
            int clusterSize = clusterSizes.get(i).intValue();
            if (clusterSize == 0) {
                emptyClusters.add(rivalClusters.get(i));
            }
            totalMembers += clusterSize;
        }

        /** Case ALL ZEROS:  Nobody has a member, purely random choice. */
        if ( emptyClusters.size() == rivalClusters.size() ) {
            int winnerIndex = r.nextInt(rivalClusters.size());
            return winner = rivalClusters.get(winnerIndex).intValue();
        }
        /** Case ONE ZERO: only one cluster has zero members and thus it is the winner. */
        else if (emptyClusters.size() == 1)  {
            return winner = emptyClusters.get(0);
        }
        /** Case SOME ZEROS : two or more classes has zero member: the winner is 
         * chosen randomly among them.
         */
        else if ( emptyClusters.size() > 1 ) {
            int winnerIndex = r.nextInt(emptyClusters.size());
            return winner = emptyClusters.get(winnerIndex).intValue();    
        }
        /** CASE NONE ZERO: the winner is chosen using weighted probability. */
        else if (emptyClusters.size() == 0) {
            
            double [] weights = new double[numRivals];

            /** Compute the weights. */
            for(int i=0;i<numRivals;i++){
                double m = (double) clusterSizes.get(i).intValue();
                double t = (double) totalMembers;
                weights[i] = m / t;
            }

            /** Organize node in RANKS. */
            ArrayList<ArrayList<Integer>> ranks = new ArrayList<ArrayList<Integer>>();
            ArrayList<Integer> firstRank = new ArrayList<Integer>();
            firstRank.add(rivalClusters.get(0));
            ranks.add(firstRank);

            /** Keep track of the rank for every rival node. */
            int [] rankPlaceHolders = new int[numRivals];
            rankPlaceHolders[0] = 0;

            int lastRank = 0;
            for (int i=1; i<rivalClusters.size(); i++) {
                /** Add to an existing rank. */
                if ( weights[lastRank] == weights[i] ) {
                    ranks.get(lastRank).add(rivalClusters.get(i));
                } else {
                    /** Create a new rank. */
                    ArrayList<Integer> rank = new ArrayList<Integer>();
                    rank.add(rivalClusters.get(i));
                    ranks.add(rank);
                    lastRank++;
                }
                rankPlaceHolders[i] = lastRank;
            }


            /* Build the CDF vector */
            double [] cdf = new double[numRivals];
            cdf[0] = weights[0];
            for(int i=1; i<weights.length; i++) {
                cdf[i] = cdf[i-1] + weights[i];
            }

            /*
            System.out.print("CDF: ");
            for(int i=0; i<weights.length; i++) {
                System.out.print( cdf[i] + ",");
            }
            */

            double threshold = r.nextDouble();
            int winnerIndex =0;

            /* Identify the winner. */
            for(int i=1; i<cdf.length; i++) {
                if ( (threshold >= cdf[i-1]) && (threshold <= cdf[i]) ) {
                    break;
                }
                winnerIndex++;
            }

            /* Retrieve the rank of the winner from the index. */
            int winnerRank = rankPlaceHolders[winnerIndex];
            /** MIRROR the winnerRank. */
            winnerRank = ranks.size() - winnerRank - 1;

            //System.out.print("The winner is : " +rivalClusters.get(winnerIndex)+ " in rank: " + rankPlaceHolders[winnerIndex]);

            /* Retrieve all the components of the rank. */
            ArrayList<Integer> winnerRankList = ranks.get(winnerRank);

            /* Only one cluster in the rank : it becomes the winner. */
            if (winnerRankList.size() == 1) {
                winner = winnerRankList.get(0);
            } else {
            /** Two or more clusters in the rank: the winner is randomly chosen among them. */
                winner = winnerRankList.get(r.nextInt(winnerRankList.size()));
            }

        //System.out.print("The winner is: " + winner );

        //System.out.print("Competitors: " + competitors.size() +" " + memberNodes.size()+ "  ");
        /*System.out.print(" Competitors: ");
        for (int i=0;i<rivalClusters.size();i++) {
            //System.out.print(rivalClusters.get(i) + "(p" + weights[i] + "M" + clusterSizes.get(i)+") " );
            System.out.print(rivalClusters.get(i) + "(SIZE:" + clusterSizes.get(i)+") " );
        }

        for (int i=0;i<ranks.size();i++) {
            ArrayList<Integer> rank = ranks.get(i);
            System.out.print("RANK " + i + ": ");
            for (int j=0;j<rank.size();j++) {
                System.out.print( rank.get(j) + ",");
            }
        }*/

        //System.out.print("R: " + r.nextDouble());

        }

        return winner;
    }

}
